#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def insert_sort(input_list):
    """直接插入排序，升序

    Args:
        input_list: 数列

    Returns:
        升序数列
    """
    length = len(input_list)
    for x in range(1, length):
        key = input_list[x]  # 要插入的数
        i = x - 1
        while i >= 0:
            if input_list[i] > key:
                input_list[i + 1]=input_list[i]
            else:
                break
            i -= 1
        input_list[i + 1] = key
    return input_list


def bubble_sort(input_list):
    """冒泡排序

    Args:
        input_list: 数列

    Returns:
        升序数列
    """
    length = len(input_list)
    for j in range(1, length):
        for i in range(length-j):
            if input_list[i] > input_list[i+1]:
                input_list[i], input_list[i+1] = input_list[i+1], input_list[i]
    return input_list


def select_sort(input_list):
    """简单选择排序

    Args:
        input_list: 数列

    Returns:
        升序数列
    """
    length = len(input_list)
    for i in range(length):
        minimum = i
        for j in range(i, length):
            if input_list[j] < input_list[minimum]:
                minimum = j
        input_list[i], input_list[minimum] = input_list[minimum], input_list[i]
    return input_list


def shell_sort(input_list):
    pass
    return input_list


def quick_sort(input_list):
    pass
    return input_list


# 堆排序
def heap_sort(input_list):
    def heap_rebuild(input_list, index, length):
        """堆排序

        Args:
            input_list: 数列
            index:
            length:
        
        Returns:
            
        """
        lchild = index * 2 + 1
        rchild = lchild + 1
        if lchild < length:
            heap_rebuild(input_list, lchild, length)
            if input_list[lchild] > input_list[index]:
                input_list[index], input_list[lchild] = input_list[lchild], input_list[index]
        if rchild < length:
            heap_rebuild(input_list, rchild, length)
            if input_list[rchild] > input_list[index]:
                input_list[index], input_list[rchild] = input_list[rchild], input_list[index]

    length = len(input_list)
    # 重建完之后最大的元素在下标为0的位置
    heap_rebuild(input_list, 0, length)
    while length > 0:
        # input_list[length-1]为末尾元素
        length -= 1
        # 交换到表尾
        input_list[0], input_list[length] = input_list[length], input_list[0]
        heap_rebuild(input_list, 0, length)
    return input_list

if __name__ == '__main__':
    L1 = [5, 9, 6]
    heap_sort(L1)
    print(L1)
